package testlist;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    static class ListNode {
      int val;
      ListNode next = null;
      public ListNode(int val) {
        this.val = val;
      }
    }
    // 链表反转
    private ListNode reverse(ListNode head) {
        if (head == null) return null;
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        return pre;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        // 思路：
        // 1.链表反转
        // 2.同时遍历两个链表(条件一个不为空)
        // 3.对应相加,保留进位
        // 4.将结果追加到结果链表(头插结果就不用反转了)
        ListNode h1 = reverse(head1);
        ListNode h2 = reverse(head2);

        int carry = 0;
        int num = 0;
        ListNode res = new ListNode(-1);

        while (h1 != null || h2 != null) {
            if (h1 != null && h2 != null) {
                num = (h1.val + h2.val + carry) % 10;
                carry = (h1.val + h2.val + carry) / 10;
                h1 = h1.next;
                h2 = h2.next;
            } else if (h1 != null && h2 == null) {
                num = (h1.val + carry) % 10;
                carry = (h1.val + carry) / 10;
                h1 = h1.next;
            } else if (h2 != null && h1 == null) {
                num = (h2.val + carry) % 10;
                carry = (h2.val + carry) / 10;
                h2 = h2.next;
            }
            // 头插
            ListNode node = new ListNode(num);
            ListNode resNext = res.next;
            res.next = node;
            node.next = resNext;
        }
        if (carry != 0) {
            // 头插
            ListNode node = new ListNode(carry);
            ListNode resNext = res.next;
            res.next = node;
            node.next = resNext;
        }

        return res.next;
    }

    /**
     * 1 3 5
     * 2 4 6
     * @param head1
     * @param head2
     * @return
     */
    private ListNode merge(ListNode head1, ListNode head2) {
        if (head1 == null) return head2;
        if (head2 == null) return head1;
        // 并的过程其实就是双链表排序
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                cur.next = head1;
                head1 = head1.next;
            } else {
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        if (head1 != null) {
            cur.next = head1;
        } else {
            cur.next = head2;
        }
        return head.next;
    }

    // 单链表排序
    public ListNode sortInList (ListNode head) {
        // write code here
        // 归并排序的思想
        if (head == null || head.next == null) return head;
        // 递归的话需要找中点，这里需要三个指针
        // left = head
        // mid = head.next
        // right = head.next.next
        // right 走两步，left、mid 走一步，
        // 可以保证最终mid指向中间结点，left指向左边最后一个结点，right指向最右结点
        ListNode left = head;
        ListNode mid = head.next;
        ListNode right = head.next.next;
        while (right != null && right.next != null) {
            left = left.next;
            mid = mid.next;
            right = right.next.next;
        }
        // 截断
        left.next = null;
        ListNode l = sortInList(head);
        ListNode r = sortInList(mid);
        return merge(l, r);
    }
}